/*
 * @Author: your name
 * @Date: 2024-05-16 10:47:24
 * @LastEditTime: 2024-05-16 11:40:14
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\51.n-皇后.cpp
 */
/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution {
public:
    vector<vector<string>> res;
    vector<pair<int, int>>path;
    bool isValid(int a, int b){
        for(int i = 0; i < path.size(); i++){
            int error_a = a - path[i].first;
            int error_b = b - path[i].second;
            if( error_b == 0 || error_a == error_b || error_a + error_b == 0){
                return false;
            }
        }
        return true;
    }
    void backtracking(int n, int startLine){
        if(startLine == n){
            string str = string(n, '.');
            vector<string> tmp(n, str);
            for(int i = 0; i < path.size(); i++){
                tmp[path[i].first][path[i].second] = 'Q';
            }
            res.push_back(tmp);
        }
        for(int i = 0; i < n; i++){
            if(!isValid(startLine, i)){
                continue;
            }
            path.push_back(make_pair(startLine, i));
            backtracking(n, startLine + 1);
            path.pop_back();
        }
    }
    
    vector<vector<string>> solveNQueens(int n) {
        backtracking(n, 0);
        return res;
    }
};
// @lc code=end

